public class Solution {
    //二分查找
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        while(left <= right) {
            mid = left + (right-left)/2;
            if(nums[mid] > target) {
                //在左半边
                right = mid - 1;
            }else if(nums[mid] < target) {
                //在右半边
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
    //在排序数组中查找元素的第一个和最后一个位置
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1;
        int[] ret = new int[]{-1,-1};
        if(nums.length == 0) {
            return ret;
        }
        int mid = 0;
        //查找左端点
        while(left < right) {
            mid = left + (right-left)/2;
            if(nums[mid] < target) {
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        if(nums[left] == target) {
            ret[0] = left;
        }
        //查找右端点
        left = 0;
        right = nums.length-1;
        while(left < right) {
            mid = left+(right - left + 1)/2;
            if(nums[mid] <= target) {
                left = mid;
            }else{
                right = mid - 1;
            }
        }
        if(nums[left] == target) {
            ret[1] = left;
        }
        return ret;
    }
    //x的平方根
    public int mySqrt(int x) {
        //[0,x]区间查找x的平方根
        long left = 1;
        long right = x;
        if(x <= 0) {
            return 0;
        }
        long mid = 0;
        while(left < right) {
            mid = left + (right - left + 1)/2;
            if(mid*mid > x) {
                right = mid - 1;
            }else{
                left = mid;
            }
        }
        return (int)left;
    }
    //搜索插入位置
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        while(left < right) {
            mid = left + (right - left)/2;
            if(nums[mid] < target) {
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        //边界情况，整个数组最后一个位置
        if(nums[left] < target) {
            return left + 1;
        }
        return left;
    }
}
